package offer;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class offerII_0078 {
    public ListNode mergeKLists(ListNode[] lists) {
        int len= lists.length;
        if(len==0) return null;
        ListNode[] head=new ListNode[len];
        PriorityQueue<indexnode> priorityQueue=new PriorityQueue<>(new Comparator<indexnode>(){
            @Override
            public int compare(indexnode o1, indexnode o2) {
                return o1.node.val-o2.node.val;
            }
        });
        for(int i=0;i<len;++i){
            head[i]=lists[i];
            if(head[i]==null) continue;
            priorityQueue.add(new indexnode(i,head[i]));
            head[i]=head[i].next;
        }
        ListNode top=new ListNode(0);
        ListNode cuurent=top;
        while(!priorityQueue.isEmpty()){
            int index=priorityQueue.peek().index;
            cuurent.next=priorityQueue.poll().node;
            cuurent=cuurent.next;
            if(head[index]!=null) {priorityQueue.add(new indexnode(index,head[index]));
                    head[index]=head[index].next;
            }
        }
        return top.next;

    }
    class indexnode{
        public int index;
        public ListNode node;
        public indexnode(){

        }
        public indexnode(int index,ListNode node){
            this.index=index;
            this.node=node;
        }
    }
}
